/************************************************************************
                        ConversionManager.h - Copyright Claudio Botta

This library is free software; you can redistribute it and/or modify it
under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.
This library is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
License for more details.

You should have received a copy of the GNU Lesser General Public License
along with this library; if not, write to the
Free Software Foundation, Inc., 51 Franklin St, Fifth Floor,
Boston, MA 02110, USA

This file was generated on Sat Mar 15 2008 at 10:58:11
The original location of this file is /home/bottac/geomagick/ConversionManager.h
/usr/share/apps/umbrello/headings/heading.h
**************************************************************************/


#ifndef CONVERSIONMANAGER_H
#define CONVERSIONMANAGER_H

#include <string>
#include <vector>
#include <sstream>


#include "ConversionRoute.h"
#include "BaseTypes/BaseType.h"

#include "BaseTypes/MeshType.h"
#include "BaseTypes/Triangles.h"
#include "BaseTypes/Polygons.h"
#include "BaseTypes/Nurbs.h"
#include "BaseTypes/WingedEdges.h"


#include "Conversion.h"
#include "Triangulizer.h"
#include "NurbsTesselator.h"
#include "Polygons2WingedEdges.h"
#include "WingedEdges2Polygons.h"

#include <boost/foreach.hpp>
#include <boost/function.hpp> // !TODO REMOVE ME

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/bellman_ford_shortest_paths.hpp>

#include "geomagickGlobal.h"



using namespace std;
using namespace boost;


namespace geomagick{
struct EdgeProperties {
        int weight;
};

struct ShortestPaths{
 vector<int>* distances;
 vector<size_t>* parents;
};

typedef pair < int, int > E;
typedef adjacency_list < vecS, vecS, directedS,
no_property, EdgeProperties> Graph;


/**
 * \class ConversionGraph
 *
 * a helper class to easier access boost C++es
 * graph capabilities
 *
 */
class ConversionGraph
{
public:
        ConversionGraph() {
                this->N = 0;
                this->n_edges = 0;
		Edges.clear();
		weights.clear();
		distance.clear();

        }

	void clear() {
		this->N = 0;
		this->n_edges = 0;
		Edges.clear();
		weights.clear();
		distance.clear();
	}	
	void addVertices(int n){
		this->N+=n;
	}	

        void addVertex() {
                this->N++;
        }
	
	string dot() {
		stringstream DOT;
		DOT << "digraph G {";
		int i = 0;
		foreach(E Edge, Edges)
		{
			
			DOT << (Edge.first) << "->" << (Edge.second) ;
			DOT << " [label=" << '"' << weights[i] <<  '"';
			if((unsigned int)Edge.first == (unsigned int)parent[Edge.second]){
			DOT << ", color=\"black\"";
			}
			else{
			DOT << ", color=\"grey\"";
			}
			DOT << " ]; \n";	
			i++;
			
		}
	
		for(int j = 0; j < N; j++)
		{
			DOT << j << " [ ];  \n";  
		}
	
		 
		DOT << "}";
		return DOT.str();
	}
	
        void addEdge(E edge, int weight) {
                // !TODO assertion that all
                // Vertice are in the list
                Edges.push_back(edge);
                weights.push_back(weight);
                n_edges++;
        }

        ShortestPaths  getShortestPaths(int Vertex) {
                Graph g(this->N);
                for (std::size_t j = 0; (unsigned int)j < (unsigned int)n_edges; ++j)
                        add_edge(this->Edges[j].first, this->Edges[j].second, g);
                graph_traits < Graph >::edge_iterator ei, ei_end;
                property_map<Graph, int EdgeProperties::*>::type
                weight_pmap = get(&EdgeProperties::weight, g);

                int i = 0;
                for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei, ++i)
			{
			#if DEBUG
			cout << "From: " << source((*ei),g) << " to: " << target(*(ei),g) << " : " << weights[i] << endl;
			#endif
			int sourceV =  source((*ei),g);
			int targetV =  target(*(ei),g);
			for(int k = 0; k <n_edges; k++){
                        if(Edges[k].first == sourceV && Edges[k].second == targetV)
				weight_pmap[*ei] = weights[k];
			}
			}

                distance =  vector<int>(N, (std::numeric_limits < short >::max)());
                parent = vector<std::size_t>(N);
                for (i = 0; i < N; ++i)
                        parent[i] = i;

                distance[Vertex] = 0;

		 bool r = bellman_ford_shortest_paths(g, int (N), weight_map(weight_pmap).distance_map(&distance[0]).
     predecessor_map(&parent[0]));
               // bool r = bellman_ford_shortest_paths(g, int(N), weight_pmap, &parent[0], &distance[0], closed_plus<int>(), std::less<int>(), default_bellman_visitor());
	#if DEBUG	
	for(unsigned int i = 0; i < (distance).size(); i++) cout << "Distance to " << i <<" : " << (distance)[i] << endl;
	for(unsigned int i = 0; i < parent.size(); i++) cout << "Parent of " << i <<" : " << (parent)[i] << endl;
	if(!r) cout << "Negative cycle ! \n";
	#endif

	/*
		// Recalculate the distances
		// There seems to be a bug in bellman_ford_shortest_paths(), distances seem to be wrong in some cases.
		// 
		
		i = 0;
		foreach(int dist, distance)
		{
			int newDist = 0;
			
			if(dist != 0)
			{
			 int predecessor = parent[i];
				if(predecessor < N && predecessor >= 0 )
				{
					newDist += DirectDistance(predecessor,i);
				}
				if(distance[predecessor] == 0)
				{
				distance[i] = newDist;
				}
			}
			i++;
			
		}
	*/
		ShortestPaths sp = {&(distance),&(parent)};
                return sp;
        }

	int DirectDistance(int from, int to)
		{
			int i = 0;
			// int dist = (std::numeric_limits < short >::max)();
			foreach(E Edge, Edges)
			{
				if(Edge.first == from && Edge.second ==  to)
					return weights[i];
				i++;
			}
			return -1;
		}
private:
        int n_edges; // number of Edges
        int N; // Number of Vertice
        vector<E> Edges;
        vector<int> weights;
        vector<int> distance;
	vector<size_t> parent;

};

/**
  * \class ConversionManager
  * Keeps Track of the availeable Conversions and BaseTypes. Finds ConversionRoutes
  */


class ConversionManager
{
public:

        // Constructors/Destructors
        //
	ConversionManager()
	{
		this->CGraph = new ConversionGraph();
		
		this->registerBaseType(Nurbs::getTypeId());
        	this->registerBaseType(Triangles::getTypeId());
        	this->registerBaseType(Polygons::getTypeId());
		this->registerBaseType(WingedEdges::getTypeId());
		//TestManager->registerBaseType(Nurbs::getTypeId());

		// Register Conversions at the ConversionManager
		this->registerConversion(Triangulizer::getTypeId());
		this->registerConversion(NurbsTesselator::getTypeId());
		this->registerConversion(WingedEdges2Polygons::getTypeId());
		this->registerConversion(Polygons2WingedEdges::getTypeId());
	}

	~ConversionManager()
	{
		delete this->CGraph;
	}
        // Static Public attributes
        //


        /**
         * @return ConversionRoute
         * @param  SourceType  
         * @param  TargetType  
         */
        ConversionRoute route (BaseType SourceType, BaseType TargetType );

	
        /**
         * @return ConversionRoute
         * @param  SourceType  !TODO Use references 
         * @param  TargetType  !TODO Use references
         */
        ConversionRoute route (std::vector<BaseTypeId*> SourceType, std::vector<BaseTypeId*> TargetType );

protected:

// Static Protected attributes
//

// Protected attributes
//

public:


// Protected attribute accessor methods
//

protected:

public:


// Protected attribute accessor methods
//

protected:


private:

// Static Private attributes
//

// Private attributes
//
vector<BaseTypeId*> BaseTypes;
vector<ConversionId*> Conversions;

ConversionGraph* CGraph;

ConversionRoute m_iConversionRouting;
public:


// Private attribute accessor methods
//

private:

void rebuildGraph();
int getVertexNumberbyName(string name);

public:


// Private attribute accessor methods
//





/**
 * Register a new BaseType. Does nothing, if the BaseType has already been registered,
 * @param BaseTypeId* a pointer to the BasetypeId of the Basetype which is to be registered
 * @return 0 on success
 */
int registerBaseType(BaseTypeId*);

/**
 * Register a new Conversion. Does nothing, if the Conversion has already been registered,
 * @param ConversionId* a pointer to the ConversionId of the Conversion which is to be registered
 * @return 0 on success
 */
int registerConversion(ConversionId*);


/**
 * @return a std::string containing the Names of all registered BaseTypes
*/
string strGetBaseTypeNames();


//int registerConverter(ConverterId*);
//string strGetConverterNames();
/**
 * @return a std::string containing the Names of all registered Conversions
*/
string strGetConversionNames();


/**
* @return a string describig the ConversionGraph for use with graphviz (www.graphviz.org).
*/
string dot(){ 
stringstream DOT;
		DOT << "digraph G {";
		int i = 0;
		foreach(ConversionId* registeredConversion, Conversions)
		{
			
			DOT << (registeredConversion->getSourceId()->getTypeName()) << "_" ;
			DOT <<  getVertexNumberbyName(registeredConversion->getSourceId()->getTypeName());
			DOT << "->" << (registeredConversion->getTargetId()->getTypeName()) << "_" ;
			DOT <<  getVertexNumberbyName(registeredConversion->getTargetId()->getTypeName()) ;
			DOT << " [label=" << '"' << registeredConversion->getEdgeWeight() <<  '"' << " ];" << "\n";	
			i++;
		}
		i = 0;
		foreach(BaseTypeId* registeredBaseType, BaseTypes)
		{
			
			DOT << registeredBaseType->getTypeName() << "_" << i <<  " [  ]; \n";
			i++;
		}
	
		 
		DOT << "}";
		return DOT.str();//

}
string CGdot(){return this->CGraph->dot(); } 
ShortestPaths getShortestPaths(int Vertex){return this->CGraph->getShortestPaths(Vertex);}
ConversionId* getConversion(int VertexFrom, int VertexTo);

private:



};
}

#endif // CONVERSIONMANAGER_H
